package com.simon.study.algorithm.tree;

import com.simon.study.algorithm.basic.ComplexSort;
import java.util.ArrayDeque;
import java.util.Deque;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/21 4:52 下午
 */
@NoArgsConstructor
public class Tree {
    @Getter @Setter
    TNode root;

    public Tree(TNode root) {
        this.root = root;
    }

    public TNode leftRotate(TNode spot){
        TNode node   = spot.right;
        spot.right   = node.left ;
        node.left    = spot;
        return node;
    }

    public TNode rightRotate(TNode spot){
        TNode node    = spot.left;
        spot.left     = node.right;
        node.right    = spot;
        return node;
    }


    public void hiarachicallyPrint(){
        Deque<TNode> queue = new ArrayDeque<>();

        if(root != null){ queue.addLast(root); }
        int pre = 0;
        for (TNode top = root; !queue.isEmpty(); top = queue.peekFirst()){
            if(top.getLeft()  != null){ queue.addLast(top.getLeft());  pre++; }
            if(top.getRight() != null){ queue.addLast(top.getRight()); pre++; }

            queue.pop(); System.out.print(top + " ");
            if(pre == queue.size()){
                pre = 0; System.out.println();
            }
        }
    }

    public int height(){
        return height(this.root);
    }

    public static TNode createMaxHeapTree(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            ComplexSort.heapAdd(arr, i);
        }
        return createFromMaxHeap(arr);
    }

    public static TNode createFromMaxHeap(int[] arr){
        TNode[] nodes = new TNode[arr.length];
        nodes[0] = new TNode(arr[0]);
        for (int i = 0; i < arr.length; i++) {
            int lci = (i<<1) + 1;
            if(lci < arr.length) {
                nodes[i].left = new TNode(arr[lci]);
                nodes[lci] = nodes[i].left;
            }else{ break; }

            if(lci+1 < arr.length) {
                nodes[i].right = new TNode(arr[lci+1]);
                nodes[lci+1] = nodes[i].right;
            }else { break; }
        }

        return nodes[0];
    }



    public static int height(TNode node){
        if(node == null){ return 0; }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    public boolean balanced(){ return balanced(this.root); }

    public static boolean balanced(TNode node){
        if(node == null){ return true; }
        if(!balanced(node.left) || !balanced(node.right)){ return false; }

        int left  = height(node.left)  + 1;
        int right = height(node.right) + 1;

        if(Math.abs(left - right ) > 1){ return false; }
        return true;
    }
}

